import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     *
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int m=matrix.length;
        int n=matrix[0].length;
        //构造一个m*n矩阵
        //填入值，第i行第j列的最小路径==matrix[i][j]的值+从上边来的值或者从左边来的值（哪个小取哪个）
        int[][] dp=new int[m][n];

        dp[0][0]=matrix[0][0];//初始化开始位置
        //第0行只能往右，先填第0行
        for(int i=1;i<m;i++){
            dp[0][i]=matrix[0][i]+dp[0][i-1];
        }
        //第0列只能往下，再填第0列
        for(int j=1;j<n;j++){
            dp[j][0]=dp[j-1][0]+matrix[j][0];
        }
        //剩下的按动态方程填
        for(int i=1;i<m;i++){
            for(int j=1;j<n;j++){
                dp[i][j]=matrix[i][j]+Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }

        return dp[m-1][n-1];//返回最后的右下角的值

    }
}